<?php
/**
 * <https://y.st./>
 * Copyright © 2017 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Paging',
	'<{subtitle}>' => 'Written in <span title="Operating Systems 1">CS 2301</span> of <a href="http://www.uopeople.edu/">University of the People</a>, finalised on 2017-10-18',
	'<{copyright year}>' => '2017',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<div class="APA_title_page">
	<p>
		Paging<br/>
		Alex Yst<br/>
		University of the People
	</p>
</div>
<h2>Introduction</h2>
<p>
	The premise of this assignment is that we have a 32-bit virtual address space, one-gibibyte of $a[RAM], and our pages are one mebibyte in length.
	A 32-bit virtual address space provides us with enough addresses for four gibibytes (2<sup>32</sup> bytes) of virtual memory.
	We are to discuss certain aspects of such a configuration.
	Finally, we were told to translate the virtual address <code>0x410423</code> to a hardware address given the following address-translation table, with all values specified in hexadecimal:
</p>
<table>
	<tbody>
		<tr>
			<td>
				Entry
			</td>
			<td>
				Number
			</td>
		</tr>
		<tr>
			<td>
				Value
			</td>
			<td/>
		</tr>
		<tr>
			<td>
				0
			</td>
			<td>
				1F
			</td>
		</tr>
		<tr>
			<td>
				1
			</td>
			<td>
				3C
			</td>
		</tr>
		<tr>
			<td>
				2
			</td>
			<td>
				55
			</td>
		</tr>
		<tr>
			<td>
				3
			</td>
			<td>
				9C
			</td>
		</tr>
		<tr>
			<td>
				4
			</td>
			<td>
				DD
			</td>
		</tr>
		<tr>
			<td>
				5
			</td>
			<td>
				EE
			</td>
		</tr>
		<tr>
			<td>
				6
			</td>
			<td>
				99
			</td>
		</tr>
		<tr>
			<td>
				...
			</td>
			<td>
				...
			</td>
		</tr>
		<tr>
			<td>
				20
			</td>
			<td>
				2F
			</td>
		</tr>
		<tr>
			<td>
				21
			</td>
			<td>
				4C
			</td>
		</tr>
		<tr>
			<td>
				22
			</td>
			<td>
				65
			</td>
		</tr>
		<tr>
			<td>
				23
			</td>
			<td>
				AC
			</td>
		</tr>
		<tr>
			<td>
				24
			</td>
			<td>
				ED
			</td>
		</tr>
		<tr>
			<td>
				25
			</td>
			<td>
				FE
			</td>
		</tr>
		<tr>
			<td>
				26
			</td>
			<td>
				100
			</td>
		</tr>
		<tr>
			<td>
				...
			</td>
			<td>
				...
			</td>
		</tr>
		<tr>
			<td>
				40
			</td>
			<td>
				11F
			</td>
		</tr>
		<tr>
			<td>
				41
			</td>
			<td>
				13C
			</td>
		</tr>
		<tr>
			<td>
				42
			</td>
			<td>
				155
			</td>
		</tr>
		<tr>
			<td>
				43
			</td>
			<td>
				19C
			</td>
		</tr>
		<tr>
			<td>
				44
			</td>
			<td>
				1DD
			</td>
		</tr>
		<tr>
			<td>
				45
			</td>
			<td>
				1EE
			</td>
		</tr>
		<tr>
			<td>
				46
			</td>
			<td>
				199
			</td>
		</tr>
		<tr>
			<td>
				...
			</td>
			<td>
				.
			</td>
		</tr>
	</tbody>
</table>
<h2>Aspects of the system</h2>
<p>
	On a paged system, a virtual address can be broken into two components: a virtual page number and an offset (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2016).
	Each address references a given byte of virtual memory, so the offset must contain enough bits to uniquely identify each byte a page contains.
	Our pages are a mebibyte in length, and a mebibyte contains 2<sup>20</sup> bytes, so <strong>twenty bits are needed for the offset</strong> <em>(question #3)</em>.
	That leaves <strong>twelve bits for the virtual page number</strong> <em>(question #4)</em>.
	From this, we can see that <strong>the address space contains 4096 pages</strong> <em>(question #1)</em>, because 2<sup>12</sup> is 4096.
	Another way we could have arrived at this number is by dividing the number of bytes in the address space (2<sup>32</sup>) by the number of bytes on each page (2<sup>20</sup>).
	This second method of determining the number pages, using division, is the intuitive way to find the number of page frames in $a[RAM].
	The $a[RAM] holds 2<sup>30</sup> bytes and our pages each hold 2<sup>20</sup> bytes, so <strong>we have 1024 page frames in $a[RAM]</strong> <em>(question #2)</em>.
	A simpler way to find this, though less intuitive, is to compare the size of the virtual address space to that of the $a[RAM].
	The $a[RAM] is a quarter of the size, so it has a quarter of the page frames needed to hold all the pages in our address space.
	As the $a[RAM] has a quarter of the space the virtual memory does, we can shave two bits off the size of the virtual page number size to find the page frame number size.
	Only <strong>ten bits are therefore needed to specify a page frame number</strong> <em>(question #5)</em>.
</p>
<h2>Address translation <em>(question #6)</em></h2>
<p>
	The low-order twenty bytes of the virtual addresses on our hypothetical system are used for page offsets, so to translate the virtual address <code>0x410423</code> into a hardware address, we need to break it into its low-order twenty bits and its high-order everything else.
	A hexadecimal digit takes up exactly four bits, so five hexadecimal digits take up our needed twenty bits.
	We can thus break up the virtual address <code>0x410423</code> into a virtual page number of <code>0x4</code> and an offset of <code>0x10423</code>.
	On our address-translation table, we see that a virtual page number of <code>0x4</code> corresponds to a page frame number of <code>0xDD</code>.
	From there, all we have to do is reattach the offset to the frame number (in other words, concatenate the two together), with the page frame identifier making up the high-order bits and the offset making up the low-order bits.
	<strong>The hardware address of the given virtual memory address in <code>0xDD10423</code>.</strong>
</p>
<h2>Conclusion</h2>
<p>
	Given relatively few details about a paging configuration, we can actually calculate everything else we need.
	Mainly, we need to know the size of the address space and the size of the pages.
	From that, we can figure out what part of a virtual address corresponds to a virtual page number and what part corresponds to an offset on the given page.
	Using the page size and the size of our physical memory (the $a[RAM]), we can also tell how many page frames we have, telling us how many pages can be loaded into $a[RAM] at once.
	Of course, some of these page frames will be reserved by the operating system and won&apos;t be available to hold actual pages, but we can still get a pretty good idea about it.
	Given those three pieces of information along with an address-translation table, we can even convert virtual addresses into hardware addresses.
</p>
<div class="APA_references">
	<h2>References:</h2>
	<p>
		Arpaci-Dusseau, R. H., &amp; Arpaci-Dusseau, A. C. (2016, July 20). Paging: Introduction. Retrieved from <a href="http://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf"><code>http://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf</code></a>
	</p>
</div>
END
);
